package _01_动态数组;

public class _441_排列硬币 {

    public static void main(String[] args) {
        _441_排列硬币 v = new _441_排列硬币();
        System.out.println(v.arrangeCoins(Integer.MAX_VALUE));
        System.out.println(Integer.MAX_VALUE);
    }

    // 二分法
    public int arrangeCoins(int n) {
        int left = 1;
        int result = left;
        int right = n;
        // 找到一个最后一个比它小的
        while (left <= right) {
            // 防止数据溢出
            long mid = left + ((right - left) >> 1);
            if ((1 + mid) * mid >> 1 <= n) {
                result = (int) mid;
                left = (int) (mid + 1);
            } else {
                right = (int) (mid - 1);
            }
        }
        return result;
    }

    // 数学公式
    public int arrangeCoins1(int n) {
        return (int) ((Math.sqrt(1 + (long)8 * n) - 1) / 2);
    }

}
